Universal Quantum Computing
Discuss the key ideas in the proof of universality; universal set of quantum gates; fidelity.
Table of Contents
1. Motivation
- Universality
- We say a set of gates is universal, if it can be used to generate any arbitrary computation.
Any legitimate unitary matrix is a proper quantum gate. However, just like classic computers, we want smaller universal gate sets, because the size affects the length of instructions and the efficiency of computation. To obtain a smaller universal gate set, we have to approximate up to an error \(\epsilon\), to quantify which, we use similarity/distance.
2. State Distance
Given states \(\ket{\psi}, \ket{\phi}\), their similarity is measured by fidelity
\[ F(\ket{\psi}, \ket{\phi}) = |\braket{\psi|\phi}|^{2} \]
The higher their fidelity is, the closer the states are. The distance between quantum state is defined as
\[ d(\ket{\psi}, \ket{\phi}) = \min_{\gamma} \| \ket{\psi} - e^{i\gamma}\ket{phi} \| \]
Note the \(e^{i\gamma}\), since states are equal up to a global phase.
Relationship between fidelity and distance
\[ d(\ket{\psi}, \ket{\phi}) = \sqrt{2(1-\sqrt{F})} \]
3. Gate Distance
Similarly, we can define distance between gates.
Suppose gate \(U,V\), the distance between them is
\[ d(U,V) = \max_{\ket{\psi}} d(V\ket{\psi}, U\ket{\psi}) = \max_{\ket{\psi}} \min_{\gamma} \| (V - e^{i\gamma}U) \ket{\psi} \| \]
3.1. Approximation of Gates
A gate of \(U'\) is said to be \(\epsilon\)-close to gate \(U\), if \(d(U', U) \le \epsilon\).
4. Universal Gate Set for Qubit Gates
The ultimate goal is: we want to find a small set of gates, such that any quantum computation can be well-approximated by a circuit consisting only of initializing qubits in \(\ket{0}\), gates from this sets, and measurement in the computational basis.
Out strategy is to divide-and-conquer: first find a set of single-qubit gates; then adding some two-qubit gate to this set, so that we can approximate any multi-qubit gates.
5. Solovay-Kitaev Algorithm
Solovay-Kitaev Algorithm
For any gate \(U\), given a (finite) universal set, there exists an algorithm that outputs a desired gate sequence no longer than \(\sim (\log (\frac{1}{\epsilon}))^{3.97}\)
Compiling Quantum Circuits
The process of compiling a quantum circuit involves:
- Human input a desired computation (a generic unitary matrix), and a threshold inaccuracy \(\epsilon\)
- The compiler compiles this unitary matrix into a sequence of universal gates
- The sequence is then passed to the quantum computer for execution